package leetcode.tree;

public class DPTree {
    public static Node getMaxBST(Node head){
        return process(head).maxBSTHead;
    }
    public static ReturnType process(Node x){
        //base case :如果子树是空树
        //系统最小为最大值
        //系统最大为最小值
        if (x==null){
            return new ReturnType(null,0,Integer.MIN_VALUE,Integer.MIN_VALUE);
        }
        //默认直接得到左树信息
        ReturnType lData = process(x.left);
        //默认直接得到右树信息
        ReturnType rData = process(x.right);
        //同时对以X为头节点的子树也做同样要求，也需要返回ReturnType描述的全部信息
        //以X为头节点的子树最小值是：左树最小，右树最小以及X的值三者中最小
        int min = Math.min(x.value,Math.min(lData.min,rData.min));
        //以X为头节点的子树最大值是：左树最小，右树最小以及X的值三者中最大
        int max = Math.max(x.value,Math.max(lData.max,rData.max));
        //如果只考虑可能性一和二，则以X为头节点的子树的最大搜索二叉树大小
        int maxBSTSize = Math.max(lData.maxBSTSize,rData.maxBSTSize);
        //如果只考虑可能性一和二，则以X为头节点的子树的最大搜索二叉树的头节点
        Node maxBSTHead=lData.maxBSTSize>=rData.maxBSTSize?lData.maxBSTHead:rData.maxBSTHead;
        //利用收集到的信息，可以判断是否存在第三中可能性
        if (lData.maxBSTHead == x.left && lData.maxBSTHead==x.right && x.value>lData.max && x.value<rData.min){
            maxBSTSize =lData.maxBSTSize+rData.maxBSTSize+1;
            maxBSTHead =x;
        }
        return new ReturnType(maxBSTHead,maxBSTSize,min,max);
    }
}
